package LeetCode1;

//递增顺序搜索树,主要思想运用中序遍历
public class Num897 {
    //定义虚拟头节点
    private TreeNode dummyHead = new TreeNode(0);
    //定义临时节点
    private TreeNode pre = dummyHead;
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        //先递归到左子树
        increasingBST(root.left);
        //将节点左子树置空
        root.left = null;
        //pre的右子树指向当前节点
        pre.right = root;
        //pre移到下一个待连接节点
        pre = pre.right;
        //再递归到右子树
        increasingBST(root.right);
        //输出虚拟头节点的右节点
        return dummyHead.right;
    }
}
